class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int n = heights.size(), ans = 0;
        vector<int> left(n, -1);
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[i] <= heights[st.top()]) {
                // 扔大的拿小的,最头上最小
                st.pop();
            }
            if (!st.empty()) {
                left[i] = st.top();
            }
            st.push(i);
            //  cout << left[i] <<' ';
        }
        // cout << endl;
        vector<int> right(n,n);
        stack<int> st2;
        for (int j = n - 1; j >= 0; j--) {
            while (!st2.empty() && heights[j] <= heights[st2.top()]) {
                st2.pop();
            }
            if (!st2.empty()) {
                right[j] = st2.top();
            }
            st2.push(j);
           //  cout << right[j] <<' ';
        }
        // cout <<endl;
        for (int i = 0; i < n; i++) {
            ans = max(ans, heights[i] * (right[i] - left[i] - 1));
        }
        return ans;
    }
};

1
class Solution {
    public:
        int maximumScore(vector<int>& nums, int k) {
            int n = nums.size();
            stack<int> st;
            vector<int> left(n, -1), right(n, n);
            for (int i = 0; i < n; i++) {
                while (!st.empty() && nums[st.top()] >= nums[i]) {
                    st.pop();
                }
                if (!st.empty()) {
                    left[i] = st.top();
                }
                st.push(i);
            }
            st = stack<int>();
            for (int i = n - 1; i >= 0; i--) {
                while (!st.empty() && nums[st.top()] >= nums[i]) {
                    st.pop();
                }
                if (!st.empty()) {
                    right[i] = st.top();
                }
                st.push(i);
            }
            // for(int i = 0;i < n;i++){
            //     cout << left[i] <<' ';
            // }
            // cout << endl;
            // for(int i = 0;i < n;i++){
            //     cout << right[i] <<' ';
            // }
            int ans = 0;
            for(int i = 0;i < n;i++){
                if(left[i] < k && right[i] > k)
                    ans = max(ans,(right[i] - left[i] - 1) * nums[i]);
            }
            return ans;
        }
    };